#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define INF 2000000000
#define FF first
#define SS second

int n, m;

vector<pair<LL, LL>> intervals;

bool check(LL d) {
  LL prev = -1LL * INF * INF;

  int cnt = 0;
  for (auto& i : intervals) {
    while (max(prev + d, i.FF) <= i.SS) {
      prev = max(prev + d, i.FF);
      cnt++;
      if (cnt >= n) break;
    }
    if (cnt >= n) break;
  }

  return (cnt >= n);
}

int main() {
  cin >> n >> m;

  intervals.resize(m);
  for (int i = 0; i < m; ++i) cin >> intervals[i].FF >> intervals[i].SS;

  sort(intervals.begin(), intervals.end());

  LL lo = 1;
  LL hi = 1LL * INF * INF;
  LL res = -1;

  while (lo <= hi) {
    LL mid = (lo + hi) / 2;

    if (check(mid)) {
      res = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  cout << res << "\n";
}
